package old_question_new_working;

import java.util.ArrayList;
import java.util.List;

/**
 * Author: 笨蛋超人不会飞
 * Date:  14:19
 */
public class q_46 {
}
class S_46 {

    //通过递归的方式解决全排列问题

    public List<List<Integer>> permute(int[] nums) {
        //特殊判断
        if(nums==null||nums.length==0){
            return null;
        }
        List<List<Integer>> result=new ArrayList<>();
        //如果只有一个数，那么练递归都不用，直接返回
        if(nums.length==1){
            List<Integer> list=new ArrayList<>();
            list.add(nums[0]);
            result.add(list);
            return result;
        }
        int len=nums.length;
        //默认值是0
        int[] tag_arr=new int[len];
        List<Integer> temp_list=new ArrayList<>();
        df(result,temp_list,tag_arr,nums);
        return result;
    }

    private void df(List<List<Integer>> result, List<Integer> temp_list, int[] tag_arr, int[] nums) {
        if (temp_list.size()==nums.length){
            result.add(new ArrayList<>(temp_list));
            return;
        }
        for (int i = 0; i < tag_arr.length; i++) {
            if(tag_arr[i]==0){
                tag_arr[i]=1;
                temp_list.add(nums[i]);
                df(result,temp_list,tag_arr,nums);
                //进行还原
                tag_arr[i]=0;
                temp_list.remove(temp_list.size()-1);
            }

        }
    }

    public static void main(String[] args) {
        int arr[]={1,2,3};
        S_46 s_46 = new S_46();
        System.out.println(s_46.permute(arr));


    }

}
